1. Technical Field
The invention disclosed broadly relates to data processing architecture and more particularly relates to improved data queue architectures.
2. Background Art
In many data processing applications, data is associated with an inherent priority for its manipulation. For example, in local area network contention resolution where several nodes connected to the network must contend for access to a common resource, it makes sense to give preferred service to those nodes whose data transmission requirements are inherently more important to the overall operation of the network. Typically, the prior art has stored the data descriptors pointing to the several sessions being handled by a node, into a prioritized order called a priority queue. As each new session and its associated priority is assigned to a particular node, that session must be organized by its priority with respect to the priorities of the existing sessions at that node. In the prior art this has been done by examining the contents of the prioritized queue representing the several existing sessions, and writing the new session descriptor into the queue at a position which is ranked in accordance to its priority value. Thus, after the writing of a new session descriptor to a priority queue at a node, the resultant queue will be organized in the order of the priority of the sessions now assigned to it. A problem arises with respect to this mode of operation, since the occurrence of assignments of new sessions to a node is random in time. Because of the asynchronous occurrence of new events or sessions which must be recorded in the prioritized queue, it becomes difficult for the prior art prioritized queue mechanisms to quickly and repeatedly respond to the entry of new data into the queue since each entry requires the assessment as to the relative priority of the new element with respect to the priorities of existing elements in the prioritized queue.
There are other data processing applications where prioritized queues are used, for example, in multiprogramming applications. One type of multiprogramming computer architecture is the work step architecture wherein multiple programs are executed by the single resource CPU by imposing a time sliced operation on the execution of each respective program. The time dimension is divided into periods and each of the several programs to be executed by the CPU is assigned a relative priority for execution. At the beginning of each time sliced period, the priority of each respective program is examined and that program having the highest priority is selected for execution during that time sliced period. Where the programs or their subroutines are assigned on an event-driven basis, the augmentation of the priority queue representing the programs to be executed, must occur in a manner which is asynchronous to the time sliced operation of the multiprogramming process. If the priority queue that keeps track of which of the several programs has the highest priority for execution during the next cycle, must be reorganized every time a new program or subroutine has its priority assigned to the queue, then the system will not be able to tolerate a rapid repetition of assignments of new programs to the priority queue and, at the same time, make available to the system an accurately identified highest priority program for execution during the next cycle.